{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "题目：\n",
    "说有一对可爱的兔子，出生后的第三个月开始，\n",
    "每一月都会生一对小兔子。当小兔子长到第三个月后，\n",
    "也会每个月再生一对小小兔子.\n",
    "\n",
    "要求：\n",
    "假设条件，兔子都不死的情况下，问每个月的兔子总数为多少\n",
    "\n",
    "思路：\n",
    "兔子的规律为数列0,1,1,2,3,5,8,13,21......似斐那波契数列的感觉"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "斐波那契数列（Fibonacci sequence），又称黄金分割数列、因数学家列昂纳多·斐波那契（Leonardoda Fibonacci）以兔子繁殖为例子而引入，故又称为“兔子数列”，指的是这样一个数列：1、1、2、3、5、8、13、21、34、……在数学上，斐波纳契数列以如下被以递归的方法定义：F(1)=1，F(2)=1, F(n)=F(n-1)+F(n-2)（n>=2，n∈N*)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [],
   "source": [
    "from __future__ import print_function\n",
    "import time"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# 采用递归的方式实现\n",
    "def Fibonacci_Recursion_tool(n):\n",
    "'''\n",
    "todo\n",
    "'''\n",
    "def Fibonacci_Recursion(n):\n",
    "    result_list = []\n",
    "    for i in range(1, n + 1): result_list.append(Fibonacci_Recursion_tool(i))\n",
    "    return result_list\n",
    "print(Fibonacci_Recursion(10))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# 循环计算每项的值\n",
    "def Fibonacci_Loop_tool(n):\n",
    "'''\n",
    "todo\n",
    "'''\n",
    "def Fibonacci_Loop(n):\n",
    "    result_list = []\n",
    "    a, b = 0, 1\n",
    "    while n > 0:\n",
    "        result_list.append(b)\n",
    "        a, b = b, a + b\n",
    "        n -= 1\n",
    "    return result_list\n",
    "print(Fibonacci_Loop(10))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# 采用迭代的方式实现\n",
    "def Fibonacci_Yield_tool(n):\n",
    "'''\n",
    "todo\n",
    "'''\n",
    "def Fibonacci_Yield(n):\n",
    "    return list(Fibonacci_Yield_tool(n))\n",
    "print(Fibonacci_Yield(10))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# 性能比较\n",
    "def Test_Fibonacci(n):\n",
    "    t1 = time.clock()\n",
    "    Fibonacci_Recursion(n)\n",
    "    t2 = time.clock()\n",
    "    l1 = t2 - t1\n",
    "\n",
    "    t1 = time.clock()\n",
    "    Fibonacci_Loop(n)\n",
    "    t2 = time.clock()\n",
    "    l2 = t2 - t1\n",
    "\n",
    "    t1 = time.clock()\n",
    "    Fibonacci_Yield(n)\n",
    "    t2 = time.clock()\n",
    "    l3 = t2 - t1\n",
    "\n",
    "    print(\"第%d次的测试结果为:\" % n, [l1,l2, l3])\n",
    "Test_Fibonacci(25)"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 2",
   "language": "python",
   "name": "python2"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 2
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython2",
   "version": "2.7.12"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}
